1. Field of the Invention
The present invention relates to operating systems for computers and computer complexes. More particularly, it describes a mechanism and process for managing the working set sizes of programs executing within a virtual memory computer complex managed by an operating system.
2. Background Art
In typical virtual memory-oriented computer complexes, many programs execute concurrently and compete for system resources including processor storage. An operating system, such as IBM's MVS/ESA, allocates resources, including processor storage (which includes central storage and expanded storage), to the programs. In so doing, the operating system "swaps" programs in and out of central storage--so that programs not currently executing (e.g.,--suspended awaiting terminal user interaction) are not unnecessarily depriving active programs of limited central storage resources. In addition, the operating system may "steal" central storage pages from swapped-in programs, which frees them up for later reallocation. The stealing of a page is helpful if the page is not soon re-referenced, but is damaging if the program from which it is stolen immediately re-references it; in this latter case it must be "demand-paged" in from expanded storage or auxiliary storage, and the stealing was in vain. An algorithm in wide use for such page-stealing is "global LRU"--or "global least-recently-used". Using this page stealing algorithm, usage characteristics of all central storage pages are maintained; a page is "stolen" from expanded or an active (swapped-in) program if it has not been referenced "recently"--when compared with the page referencing characteristics of other system pages. The theory behind such a global LRU policy is that the pages most recently referenced by a program are those most likely to be referenced in the near future--so, in general, "old" pages should be stolen first. It is recognized that such policies may not be helpful for programs with "unusual" referencing patterns--for example, programs sequentially referencing in-storage data will not be helped by LRU stealing.
A concept that has proven useful in handling central storage management in such systems is that of a program's "working set". As commonly used, a program's working set is the set of distinct pages that it references during some time interval T. Depending on the time interval chosen, a page once part of a program's working set may subsequently fall outside that set-in which case it may be treated differently from working set pages (for example--it may be stolen; it may not be swapped-in when the associated program is swapped in; etc.).
Practical difficulties arise in the implementation of a working set-based storage management policy in a complex large system environment such as the aforementioned MVS/ESA. For example, page stealing using a system-wide policy such as global LRU may not be sufficiently sensitive to individual program idiosyncrasies; a stealing scheme tailored to individual programs may be wasteful of processing resource when central storage is not in heavy demand (i.e., when there are a good deal of "discretionary" page frames--whose stealing would not adversely affect program performance, assuming such "discretionary" frames could be easily identified); viewing program working sets from the standpoint of a sliding window (i.e., over a time interval T) will not deal well with programs that periodically revert to "old habits"--i.e., "old" performance characteristics are lost, and so are unavailable for use in making new swap/steal decisions; LRU-based stealing may not be appropriate for programs with a tendency to utilize extremely large amounts of central storage; and common working set management techniques may not have a beneficial effect on productive system usage since distinctions may not be made regarding how programs use the system (i.e., performing useful work, or "thrashing"--causing excessive demand paging).